const RED = true
const BLACK = true

class Node {
  constructor (key, value) {
    this.key = key
    this.value = value
    this.left = null
    this.right = null
    this.color = RED // 默认节点颜色为红色
  }
}

class RBTreeMap {
  constructor (compare = (a, b) => {
    if (a > b) {
      return 1
    } else if (a < b) {
      return -1
    } else {
      return 0
    }
  }) {
    this._root = null
    this._size = 0
    this._compare = compare
  }

  getSize () {
    return this._size
  }

  // 对节点y进行向左旋转操作，返回旋转后新的根节点x
  //    y(node)                       x
  //  /  \                          /   \
  // T1   x      向左旋转 (y)       y     z
  //     / \   - - - - - - - ->   / \   / \
  //   T2  z                     T1 T2 T3 T4
  //      / \
  //     T3 T4
  _leftRotate (node) {
    const x = node.right
    node.right = x.left
    x.left = node
    x.color = node.color
    node.color = RED
    return x
  }

  // 对节点y进行向右旋转操作，返回旋转后新的根节点x
  //        y(node)                        x
  //       / \                           /   \
  //      x   T4     向右旋转 (y)        z     y
  //     / \       - - - - - - - ->    / \   / \
  //    z   T3                       T1  T2 T3 T4
  //   / \
  // T1   T2
  _rightRotate (node) {
    const x = node.left
    node.left = x.right
    x.left = node
    x.color = node.color
    node.color = RED
    return x
  }

  // 颜色翻转
  _flipColors (node) {
    node.color = RED
    node.left.color = BLACK
    node.right.color = BLACK
  }

  /*
  添加K,V
   */
  add (key, value) {
    this._root = this._add(this._root, key, value)
    this._root.color = BLACK // 根节点为黑色
  }

  _add (node, key, value) {
    if (node === null) {
      this._size++
      return new Node(key, value)
    }
    if (this._compare(node.key, key) > 0) {
      // 插入到左子树中
      node.left = this._add(node.left, key, value)
    } else if (this._compare(node.key, key) < 0) {
      // 插入到右子树中
      node.right = this._add(node.right, key, value)
    } else {
      node.value = value // 更新操作
    }
    if (this._isRed(node.right) && !this._isRed(node.left)) {
      node = this._leftRotate(node)
    }

    if (this._isRed(node.left) && this._isRed(node.left.left)) {
      node = this._rightRotate(node)
    }
    if (this._isRed(node.left) && this._isRed(node.right)) {
      this._flipColors(node)
    }
    return node
  }

  /*
  通过key获取value
   */
  get (key) {
    const node = this._getNode(this._root, key)
    return node === null ? null : node.value
  }

  _getNode (node, key) {
    if (node === null) {
      return null
    }
    if (this._compare(node.key, key) === 0) {
      return node
    } else if (this._compare(node.key, key) > 0) {
      // 找左子树
      return this._getNode(node.left, key)
    } else {
      return this._getNode(node.right, key)
    }
  }

  _isRed (node) {
    if (!node) {
      return BLACK
    }
    return node.color
  }

  set (key, value) {
    const node = this._getNode(this._root, key)
    if (!node) {
      throw new Error('key is not exist')
    }
    node.value = value
  }

  /*
  检测是否包含key,value
   */
  contains (key) {
    return this.get(key) !== null
  }

  /*
  获取最小值节点
   */
  _minimum (node) {
    if (node.left === null) {
      return node
    }
    return this._minimum(node.left)
  }

  /*
  删除最小值节点
   */
  _removeMin (node) {
    if (node.left === null) {
      const rightNode = node.right
      node.right = null
      this._size--
      return rightNode
    }
    node.left = this._removeMin(node.left)
    return node
  }

  remove (key) {
    const node = this._getNode(this._root, key)
    if (node !== null) {
      this._root = this._remove(this._root, key)
      return node.value
    }
    return null
  }

  _remove (node, key) {
    if (node === null) {
      return null
    }
    if (this._compare(node.key, key) > 0) {
      // 删除左孩子
      node.left = this._remove(node.left, key)
      return node
    } else if (this._compare(node.key, key) < 0) {
      // 删除右孩子
      node.right = this._remove(node.right, key)
    } else {
      // 区别对待左右子树为空的情况
      if (node.left === null) {
        const rightNode = node.right
        node.right = null
        this._size--
        return rightNode
      }

      if (node.right === null) {
        const leftNode = node.left
        node.left = null
        this._size--
        return leftNode
      }

      // 左右子树均存在, 找比删除节点大的最小节点(右子树中的最小值)
      const successor = this._minimum(node.right)
      successor.right = this._removeMin(node.right)
      successor.left = node.left

      node.left = node.right = null
      return successor
    }
  }
}

export default RBTreeMap
